/*
 * @Author: your name
 * @Date: 2021-06-26 15:13:17
 * @LastEditTime: 2021-06-26 16:26:28
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \51\main.cpp
 */
#include <iostream>
#include <vector>
using namespace std ;

vector<vector<string> > result ;
void NQ(int n,int row,vector<string> temp)
{
    if(row==n)
    {
        result.push_back(temp);
        return ;
    }
    string str(n-1,'.');
    if(row==0)
    {
        for(int i =0;i<n;++i)
                {
            str.insert(i,1,'Q');
            temp.push_back(str);
            NQ(n,row+1,temp );
            temp.pop_back();
            str.erase(i,1);
        }
    }
    else{
    int pos =temp[row-1].find('Q');
    for(int i=0;i<n;++i)
    {
        bool flag=true;
        if(i<=pos+1&&i>=pos-1)
            continue;
        for(int j = 0 ;j<row;++j)
        {
            if(temp[j][i]=='Q'||((i-row+j)<0?false:temp[j][i-row+j]=='Q')||((i+row-j)>=n?false:temp[j][i+row-j]=='Q'))
                {
                    flag=false;
                    break;
                }
        }
        if(flag)
        {
            str.insert(i,1,'Q');
            temp.push_back(str);
            NQ(n,row+1,temp );
            str.erase(i,1);
            temp.pop_back();
        }
    }
}
}
int main(int, char**) {
    vector<string> temp;
    NQ(5,0,temp);
    for(int i =0;i<result.size();++i)
    {
        cout <<"solution"<<i<<endl;
        for(int j =0;j<result[i].size();++j)
        cout<<result[i][j]<<endl;
        cout <<"********"<<endl;
    }
}
